Subject: loop detection protocol proposal

From: [email-masked]
Date: Wed, 09 Feb 94 20:09:58 -0500

Choon -

I have looked over your proposal and have a couple of detailed
questions/comments plus a general question - the detailed questions/comments
are noted in the following copy of your message from 1/26/94.

The general question is this: how do we know that the loop command and
response LPDUs will be passed reliably (or at all) through all the bridges,
routers, or other devices that will pass the broadcast TEST command LPDUs and
responses used for the CANUREACH/ICANREACH process?  At a minimum, this would
seem to require a retransmission requirement for the loop command LPDUs, that
the same SAPs be used for the loop command LPDUs as for the broadcast TEST
command LPDUs, and that the same MAC/RIF addressing be used for the loop
command LPDUs as for the broadcast TEST command LPDUs.

Norm Rehn (BBN)

>
>
>
>Section 0: Background Information
>---------------------------------
>
>In the topology of parallel DLSw (multiple DLSw paths between
>two LAN segments), multiple DLSw paths can be established, 
>resulting in duplicate frames between the end stations.
>
>
>	|                                |
>   X----|                                |----Y
>	|  |-----|             |-----|   |
>	|--|  J  |-------------|  K  |---|
>	|  |-----|             |-----|   |
>	|                                |
>	|  |-----|             |-----|   |
>	|--|  L  |-------------|  M  |---|
>	|  |-----|             |-----|   |
>	|                                |
>    LAN segment A		     LAN segment B
>
>
>For example, in the above topology, when X sends out a TEST frame,
>it gets picked up by both J and L, then sent across the Data Link
>Switch to LAN segment B. The TEST response from Y will result in
>both DLSw circuits (J-K and L-M) being established. Subsequently,
>every frame that X sends out results in 2 frames on LAN segment B,
>and vice versa for frames that Y sends out.
>
>With the proposed loop detection scheme, this multiple circuit
>(or loop) can be prevented. Before K and M sends out the TEST
>frame onto LAN segment B, they each send out a Loop Detection 
>frame to discover the existance of alternate path between the
>LAN segments. When the DLSw receive the loop detection frame, 
>the loop detection ID (which is a tie-breaker) in the frame is 
>compared with its own, and the loser will terminate its circuit
>establishment process, thus ensuring only one DLSw path between
>the LAN segments.
>
>This scheme also prevents loop from forming when the DLSw is across
>two bridged segments. E.g., in the diagram above, L-M are assumed
>to be datalink bridges. TEST frame will again get to LAN segment
>twice. The TEST frame that gets on LAN segment B via the bridges
>(i.e. L-M), results in a CANUREACH to flow in the direction of K-J
>will result in immediate termination of the DLSw path J-K, due to 
>the new DLSw state machines introduced by this scheme.
>
>
>Section 1: The Loop Detection Proposal
>--------------------------------------
>
>The gist of this proposal is as follows:
>o when a CANUREACH is received, the DLSw first tries to discover 
>  the existance of multiple DLSw paths between the origin and
>  target stations.
>
>o if multiple paths exist, the DLSw selects unambiguously the
>  DLSw pair to use.
>
>o if the DLSw receives a TEST request on its DLC, followed by a
>  CANUREACH from its DLSw partner, it terminates the circuit
>  establishment immediately.
>
>o NETBIOS UI frames are examined to determine where it originates
>  from, and remembered so that it does not loop indefinitely
>  in the network.
>
>
>This proposal has the following characteristics:
>(1) It is a reactive mechanism; it tries to detect the presence
>    of a loop only when there is a need to do so.
>
>(2) It does not require the DLSw cloud to be full mesh. It
>    assumes that each DLSw has a set of known DLSw partners.
>
>(3) It allows parallel DLSw to exist (parallel DLSw is defined as
>    multiple DLSw crcuit between two LAN segments).
>
>(4) It allows DLSw to exist across bridged LAN.
>
>(5) Plug and play. No configuration of DLSw needed, except for
>    parameter tuning.
>
>
>Section 2: Loop Detection PDUs
>------------------------------
>
>    I. (12/14 bytes) - MAC header
>	    (6 bytes) - DA (see Note 1)
>	    (6 bytes) - SA - MAC addr of DLSw that sends out this PDU
>	    (2 bytes) - Length (present if 802.3)
>
>	Note 1:
>	If Loop Detection Command frame,
>	    DA = DLSw functional address (TBD)
>	Otherwise (Loop Detection Response frame)
>	    DA = MAC address of the DLSw that this PDU is
>		 responding to
>
>    II. (3 byte) - LLC header
>	    (1 byte) - DSAP (TBD)
>	    (1 byte) - DSAP (TBD)

I presume the second DSAP should be SSAP. (See note at beginning on suggestion
for SAP assignment).

>	    (1 byte) - Control (x'03')
>
>    III. (26 bytes) - Loop Detection PDU
>	
>	+-+-+------+------+-+-+-+---------+
>	|a|b|  c   |  d   |e|f|g|    h    |
>	+-+-+------+------+-+-+-+---------+
>
>	a (1 byte) - PDU type
>	    x'00' - Loop Detection Command
>	    x'01' - Loop Detection Response
>
>	b (1 byte) - Version number
>	    x'00'
>
>	c (6 bytes) - Target MAC address
>
>	d (6 bytes) - Origin MAC address
>
>	e (1 byte) - Target Link SAP
>
>	f (1 byte) - Origin Link SAP
>
>	g (1 byte) - Loop resolving state
>	    x'00' - LOOP_RESOLVING (if DLSw state is LOOP_RESOLVING)
>	    x'01' - LOOP_RESOLVED
>	    
>	h (9 bytes) - Loop Detection Identifier
>	  this is a tie-breaker among parallel DLSw to determine
>	  which DLSw to use. It is comprised of 2 parts:
>	    (1 byte) - priority (0 .. 255)
>	    (8 bytes) - IP_addresses
>	        computed by concatenation of IP address pair (IP 
>	        address of origin and target DLSw), with the smaller 
>	        IP address value occupying the first 4 bytes
>

In cases where the DLSw does not have a TCP connection (both target and
originator are local to the same DLSw), what IP address value would be used?
(The configuration would be an alternate to the one you drew in section 0,
with the K and M units not present).

>
>
>Section 3: Modification to the DLSw state machine
>-------------------------------------------------
>
>(1) New States
>	Two new states are proposed:
>
>	CIRCUIT_SEARCHING
>	    The DLSw is awaiting a ICANREACH (after sending
>	    a CANUREACH), or a NETBIOS_NR (after sending a 
>	    NETBIOS_NQ).
>
>	LOOP_RESOLVING
>	    The target DLSw is awaiting for expiration of 
>	    Loop_Detection timer, upon which time a DLC_START_DL 
>	    or NB_Name_Query can be sent to its DLC.
>
>(2) New Events
>	LD_TIMER_EXP
>	    Expiration of Loop Detection Timer.
>
>	DLC_LD_CMD
>	    DLC received a Loop Detection Command.
>
>	DLC_LD_RSP
>	    DLC received a Loop Detection Response.
>
>(3) New Actions
>	SET_LD_TIMER
>	    Start Loop Detection Timer.
>
>	DLC_LD_CMD
>	    DLC send a Loop Detection Command.
>
>	DLC_LD_RSP
>	    DLC send a Loop Detection Response.
>
>(4) New SSP message
>	HALT_CIRCUIT
>	    stop this circuit from being established.
>
>(5) State Transition Table
>	
>	(a) CIRCUIT_SEARCHING
>	    -----------------
>	Event                Actions            Next State
>	-----                -------            ----------
>	Receive ICANREACH    Send REACH_ACK,    CIRCUIT_ESTABLISHED
>	                     DLC_RESOLVE_R
>
>	Receive NETBIOS_NR   Send REACH_ACK,    CIRCUIT_ESTABLISHED
>			     DLC_DGRM
>
>	Receive CANUREACH    Send HALT_CIRCUIT  DISCONNECTED
>
>	DLC_DGRM             Send DATAFRAME
>	except                   (note 1)
>	NB_Name_Query,
>	NB_Name_Response
>
>
>	Note 1: If the frame source address has been seen previously
>		from the same interface, or is seen for the first 
>		time, then send DATAFRAME.
>		Otherwise, the Netbios datagram is discarded.
>
>	This state is added to the DLSw state machine to differentiate
>	from the DISCONNECTED state, for the origin DLSw (the one 
>	that is waiting for a ICANREACH). It also allow for immediate 
>	termination of circuit establishement when a loop is detected 
>	(when CANUREACH is received after DLC_RESOLVE_C had been
>	received).
>
>	This state is entered into from DISCONNECTED state, after
>	the receipt of DLC_RESOLVE_C, and a CANUREACH is sent.
>
>	For SNA, the CIRCUIT_SEARCHING state is exited upon receipt
>	of ICANREACH frame, thereupon a Test response is sent to the
>	origin station, and a REACH_ACK sent to the target DLSw.
>
>	For NETBIOS, the state is exited upon receipt of NETBIOS_NR
>	frame, thereupon a NB_Name_Recognized frame is sent to the
>	origin station, and a REACH_ACK sent to the target DLSw.
>
>
>	(b) LOOP_RESOLVING
>	    --------------
>	Event                Actions            Next State
>	-----                -------            ----------
>	DLC_LD_CMD           DLC_LD_RSP
>			         (note 2)       (note 2)
>
>	DLC_LD_RSP           (note 2)           (note 2)
>
>	LD_TIMER_EXP         DLC_START_DL       RESOLVE_PENDING
>				 (note 3)
>
>	DLC_DGRM             Send DATAFRAME
>	except                   (note 1)
>	NB_Name_Query,
>	NB_Name_Response
>
>
>	Note 1: If the frame source address has been seen previously
>		from the same interface, or is seen for the first time,
>		then send DATAFRAME.
>		Otherwise, the Netbios datagram is discarded.
>
>	Note 2: If the PDU's Loop Detection ID (priority + IP address 
>		pair) is smaller than the DLSw's, or the PDU's 
>		loop_resolving_state has a value of LOOP_RESOLVED, a 
>		HALT_CIRCUIT is sent, and the state DISCONNECTED is 
>		entered.

Wouldn't we want those loop detection ID's that are higher priority to win over
the lower priority ones (it seems like this algorithm does the reverse of
that)?

>
>	Note 3: For NETBIOS, it is DLC_DGRM (send NB_Name_Query).
>
>	This state is added to the DLSw state machine to allow loop
>	detection to precede the actual sending out of TEST or
>	NB_Name_Query frame.
>
>	This state is entered into from DISCONNECTED state, after
>	the receipt of CANUREACH. It will then attempt to discover
>	the existance of multiple DLSw paths between the origin and
>	target stations by sending loop detection command frame out 
>	its DLC. At the same time, a loop detection timer is activated.
>
>	While in this state, if a loop detection command is received
>	(see note 4), a loop detection response (loop_resolving_state 
>	set to LOOP_RESOLVING) is returned. 
>	
>	When a loop detection frame (either loop detection command 
>	or loop detection response) is received, a check is made on 
>	whether the circuit establishment for the stations should 
>	continue. If the PDU has a loop_resolving_state value 
>	of LOOP_RESOLVED (indicating that there is currently another 
>	path between the stations), or that the PDU's loop_detection_id
>	has a smaller value (indicating that another DLSw pair is
>	attempting to establish a circuit for the same two stations,
>	and that DLSw pair has a better tie-breaker), then this
>	circuit should be terminated immediately.
>
>
>	Note 4: the loop detection PDU is looked at only if these
>		4-tuple (DA, SA, DSAP, SSAP) are the same as the circuit.
>
>
>	(c) DISCONNECTED
>	    ------------
>
>	Several state transititons are altered due to the addition
>	of the new states. The following state table reflects the
>	proposed table for DISCONNECTED state:
>
>	Event                Actions            Next State
>	-----                -------            ----------
>	Receive CANUREACH    SET_LD_TIMER,      LOOP_RESOLVING
>			     DLC_LD_CMD
>	Receive NETBIOS_NQ   SET_LD_TIMER,      LOOP_RESOLVING
>			     DLC_LD_CMD
>	DLC_RESOLVE_C        Send CANUREACH     CIRCUIT_SEARCHING
>	DLC_DGRM             If NB_Name_Query:  CIRCUIT_SEARCHING
>			     Send NETBIOS_NQ
>			     Else:
>			     Send DATAFRAME
>				 (note 1)
>	Receive DATAFRAME    DLC_DGRM
>				 (note 2)
>
>
>	Note 1: If the frame source address has been seen previously
>		from the same interface, or is seen for the first time,
>		then send DATAFRAME.
>		Otherwise, the Netbios datagram is discarded.
>
>	Note 2: If the origin MAC address has been seen previously
>		from the same interface, or is seen for the first time,
>		then DLC_DGRM.
>		Otherwise, the DATAFRAME is discarded.
>
>
>	(d) RESOLVE_PENDING, CIRCUIT_PENDING
>	    --------------------------------
>
>	Add the following new event to deal with receipt of loop
>	detection command frame:
>
>	Event                Actions            Next State
>	-----                -------            ----------
>	DLC_LD_CMD           DLC_LD_RSP
>	                         (note 1)
>
>	
>	Note 1: respond with loop_resolving_state set to LOOP_RESOLVED.
>	
>
>
>Section 4: NETBIOS frames learning
>----------------------------------
>
>The Netbios UI frames (NB frames beside NB_Name_Query and
>NB_Name_Recognized) can loop indefinitely in a parallel DLSw 
>topology. To avoid this from happening, a Netbios table is required
>to keep track of the source of such frames. 
>
>For these Netbios UI frames, the source address of the DLC_DGRM (or 
>DATAFRAME) are stored in a Netbios address table, together with the 
>interface that it is received on. Subsequent NETBIOS UI frames are 
>checked against the table. If the interface is different from the 
>stored value, the Netbios frame is not propagated.
>
>Each entry in the Netbios table is aged out after they are in the
>table for some specific time (time value TBD). The aging mechanism is 
>implementation specific.
>
>
>
>
>

---

From: Choon Lee <[email-masked]>
Date: Thu, 10 Feb 1994 09:07:14 -0800

Norm,

Thanks for your input. My comments below.

Regards,
Choon
3Com Corp

>> From [email-masked] Wed Feb  9 17:39:06 1994
>> To: [email-masked]
>> Subject: loop detection protocol proposal
>> Date: Wed, 09 Feb 94 20:09:58 -0500
>> From: [email-masked]
>> Content-Length: 13354
>> 
>> 
>> Choon -
>> 

Retransmissions of loop detection PDUs seems like a good idea.

MAC/RIF addressing probably would not be applicable. The loop detection is
used primarily for transparent domain (as opposed to source routing, which
do not have the loop problem - ignoring the complicated scenerio of multiple
"DLSw clouds" for now). As for the MAC addressing scheme, the DA for the TEST
command is the target end station, whereas the loop detection command PDU 
DA need to be a functional address to get to other DLSw on the same LAN
segment.

As for SAP values, I try to have the DLSw listening on only one SAP. In the
event that different TEST commands using different SAPs, if loop detection PDU
uses the SAPs as the TEST commands, then DLSw would have to listen on 
multiple SAPs. We can certainly discuss this further.

>> I presume the second DSAP should be SSAP. (See note at beginning on suggestion
Yes. SSAP it is.

>> with the K and M units not present).
Using DLSw in place of a local bridge? Hmm... interesting.
Since we don't have IP addresses to dork with, one thought that comes to mind
would be to use the DLSw MAC address instead (Pick any one MAC address from
the 2 interfaces), and pad the rest of the Loop_detection_ID field to 0.

>> the lower priority ones (it seems like this algorithm does the reverse of
A smaller number in the priority denotes higher priority. Sounds conter-intuitive,
but in keeping with the way priority values are assigned for 802.1D spanning 
tree algorithm :-)